package 二叉树中和为某一值的路径;

import java.util.ArrayList;

//题目描述
//输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。
// 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
public class Solution
{
    ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> list=new ArrayList<Integer>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target)
    {
        //前序遍历，不合适的话回滚
        if (root==null)
            return result;
        list.add(root.val);
        target-=root.val;
        if (target==0&&root.left==null&&root.right==null)
            result.add(new ArrayList<>(list));//每次都创建新的一个ArrayList，符合题目的要求
        //前序遍历
        FindPath(root.left,target);
        FindPath(root.right,target);
        //一般遍历到叶子结点，会连续遍历上面两个FindPath，然后就走下一步，进行移除结点，不会导致原结点不删除
        //仅适用于求根节点到叶子节点的情况
        //回滚
        list.remove(list.size()-1);
        return result;
    }

    public static void main(String[] args)
    {
        TreeNode node1 = new TreeNode(8);
        TreeNode node2 = new TreeNode(6);
        TreeNode node3 = new TreeNode(10);
        TreeNode node4 = new TreeNode(5);
        TreeNode node5 = new TreeNode(7);
        TreeNode node6 = new TreeNode(9);
        TreeNode node7 = new TreeNode(11);
        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;
        node3.right=node7;
        Solution solution = new Solution();
        System.out.println(solution.FindPath(node1,29));
    }
}
